The present relates invention primarily to methods and apparatus for a graphic display to insure a visually natural image by joining intermediate points between four or more given points. The intermediate points between four or more given points are necessary to produce smooth curves. For example, when ordered points such as A, B, C, D, E, F, G, H, . . . are known, the present invention can be used to produce smooth curves by joining intermediate points, between those points and, furthermore, intermediate points of the intermediate points.
In computer graphics systems, mathematical conditions for continuity are important, but the most critical task is to obtain data which appears natural when presented in terms of discrete pixels. Interpolation methods did not always play an important role in computer graphics, and were originally used as a supplementary tool to obtain finer resolution. Consequently, former indirect interpolation methods such as those that fit orthogonal functions to the given data, and then obtained interpolation values from those functions, were clearly not optimum methods. Curves generated using polynomial or Fourier series interpolation methods sometimes appear unnatural as a result of oscillations occurring at bend points. The spline function method was developed to overcome this problem, but spline functions also produce overshoot for certain data. As a further improvement Ackland has proposed the osculatory interpolation method, but it also generates some small oscillations as well as requiring excessive computation time. Akima has reported the development of an interpolation method which produces naturally appearing results with negligible oscillations by local area determination of polynomial coefficients. However, Akima's method requires the use of floating point arithmetic, and therefore computation is slow. The graphics method of the present invention considers only those given data points in the area of the point to be evaluated, and omits information from given data points which have little effect in that area. This local area approach results in interpolated values which have little oscillation error. In applying the graphics method of the present invention to various given graphics data, it has been found that the interpolation error increases rapidly as the reciprocal of the weighted coefficient L is reduced below a value of 10, but decreases between 10 and 20 giving exceptionally accurate results. Suitable selection of the weighted coefficient results in an extremely simple interpolation algorithm which has enormous practical value in computer graphics applications.
Former approaches to graphic data interpolation are detailed in the following.
A curve lying in the XY plane can be expressed parametrically as X=F(m) and Y=G(m), where m is the parameter. Likewise, a surface in three space (XYZ coordinates) can be expressed parametrically as X=F(m), Y=G(m), and Z=H(m), where again m is the parameter. Now let [X.sub.i, g(X.sub.i)], (i=1, 2, . . . , n) be an array of points formed by an ordered arrangement of discrete data from some measurement or from computation within the computer. Using parametric expression, any arbitrary point array can be converted to a collection of single valued point arrays. Therefore, [X.sub.i, g(X.sub.i)] can be assumed to be single valued without any loss of generality. Here, each g(X.sub.i) corresponds to the given data at each X.sub.i. Let the interval delta.sub.i =[X.sub.i, X.sub.i+1 ], (i=1, 2, . . . n-1) be designated the interpolation interval, and let P.sub.i be an arbitrary point within the interpolation interval delta.sub.i. When the data points g(X.sub.i), (i=1, 2, . . . , n) are known, the determination of the unknown value f(P.sub.i), corresponding to the point P.sub.i, is called interpolation or curve fitting.
Methods which determine interpolated values are categorized as either direct or indirect interpolation methods. In direct interpolation, such as in the method of this invention, interpolated values are directly determined from given data points in the vicinity of the point to be evaluated. Since directly interpolated values are computed from local data, irrespective of global conditions, calculations can be performed in parallel.
In formerly employed indirect interpolation, interpolated values are determined in two steps. First, coefficients are determined for a polynomial curve which passes through the given data points. Next, interpolated values are determined at interpolation point locations substituted into the previously determined polynomial function. Since local determination of polynomial coefficients is very difficult, indirect interpolation is not suitable for parallel computation.
In indirect interpolation, m parameters Qi (i=1, 2, . . . , m) are determined from the given data g(X.sub.i), (i=1, 2, . . . ,n). Here q.sub.i are the coefficients of the interpolation function. ##EQU1## Hence, it is necessary to solve n equations for m variables. Indirect interpolation includes methods such as the Lagrange interpolation method and the spline function method. In the Lagrange method, m=n, and all the unknowns are completely determined, but in the spline function method employing third order polynomials (cubic splines), m=n+2. In this case, since the number of unknowns exceeds the number of equations, the m parameters q.sub.i (i=1, 2, . . . , m) are determined by introducing two boundary conditions, such as the "natural cubic spline" conditions. The interpolation function T is thus determined once the coefficients (q.sub.1, q.sub.2, . . . , q.sub.m) are known. The interpolated value at the point P.sub.i is then solved by substituting the coordinates of P.sub.i into the function T. EQU f(P.sub.i)=T(P.sub.i ; q.sub.1, q.sub.2, . . . , q.sub.m)
Indirect interpolation methods have the following shortcomings. As the number of unknowns m increases, the number of computations required to solve the equations containing these unknowns increases as the square of m. This requires excessive computation time and reduces overall processing efficiency. Further, because of memory usage considerations, certain programs, such as some CAD programs, place restrictions on the number of data points which can be handled. Still further, since floating point arithmetic is used to solve indirect interpolation equations, additional processing time is required, and the effects of rounding error must be considered.
Since the m parameters q.sub.i (i=1, 2, . . . ,m) are determined based on data over the entire region to be interpolated, indirect interpolation values are effected by distant data points. Consequently, unnatural oscillations or wiggles develop when indirect methods are applied to regions which contain rapidly varying data. These oscillations are called the "Runge phenomenon" for the Lagrange interpolation method, and the "Gibbs phenomenon" for indirect interpolation employing Fourier series. In the spline function interpolation method, polynomial coefficients are determined for each interpolation interval within the interpolation region, thereby reducing the effects of distant data points on the interpolated value. However, in the spline function method employing an n'th order spline function, continuity is required at interpolation interval boundaries for derivatives up to the n-1'st order. Akima has shown that for interpolation intervals having large valued derivatives, spline function oscillations are transmitted to neighboring interpolation intervals via derivatives, thereby reducing the interpolation accuracy. To prevent the propagation of oscillations, schemes such as the rational spline function method and Akima's interpolation method have been proposed. Akima's method determines polynomial coefficients based on local data values, and obtains good results even for sharp data variations where normal spline function methods produce oscillation. Results of numerical experiments show that accuracy is improved by using only M given data points in the local area of the point to be interpolated rather than the entire set of given data points. Further numerical experiments are necessary to determine the optimum value of M. Akima's method uses four points adjacent to interpolation interval boundaries to determine slopes at those boundaries, and finds the corresponding interpolation point value using a cubic polynomial. Hence, when the interpolation value is determined locally, oscillation propagation is suppressed, and good results are obtained.